/**
 * 给定一个链表，返回链表开始入环的第一个节点,
 * 如果链表无环，则返回 null.
 * 思路:双指针法,利用快慢指针:fast一次移动两步,slow一次移动一步.
 * 1.先判断是否有环:如果fast = slow,那么这个链表有环.
 * 2.找到这个环的入口在哪:
 * 设x为head到环入口的距离,
 * y为相遇节点到入口的距离,
 * z为环剩余的长度,
 * n为fast转了几圈才遇到的slow.
 * 所以slow走过的距离为x+y , fast走过的距离为x+y+n(y+z).
 * 显然有(x+y)*2 = x+y+n(y+z)  =>  x+y = n(y+z) => x=n(y+z)-y  => x = (n-1)(y+z) + z;
 * 当n=0时,有x=z;所以可以在head处定义一个index1,在相遇节点定义一个index2,让index1和index2每次移动一步,
 * index1和index2相遇的地方就是环的入口位置.
 */

class ListNode {
  constructor(val, next) {
    this.val = val;
    this.next = next;
  }
}

var detectCycle = function (head) {
  if (!head || !head.next) { return null }
  let slow = head.next, fast = head.next.next;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (fast === slow) {
      slow = head;
      while (fast !== slow) {
        slow = slow.next;
        fast = fast.next;
      }
      return slow;
    }
  }
  return null;
}